package offer;

import java.util.*;

/**
 * @Author Elephas
 * @Date 2022/2/9
 **/
public interface CountKDifference {
    int countKDifference(int[] nums, int k);
}
class CountKDifferenceImpl1 implements CountKDifference{
    /**
     * 暴力解法
     * @param nums
     * @param k
     * @return
     */
    @Override
    public int countKDifference(int[] nums, int k) {
        int n = nums.length;
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if(Math.abs(nums[i] - nums[j]) == k){
                    count++;
                }
            }
        }
        return count;
    }
}
class CountKDifferenceImpl2 implements CountKDifference{

    /**
     * 排序 + 双指针，好像做不出来
     * @param nums
     * @param k
     * @return
     */
    @Override
    @Deprecated
    public int countKDifference(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length;
        int left = 0, right = n - 1;
        int count = 0;
        while(left < right){
            if(nums[right] - nums[left] == k){
                count++;
                int curLeft = left;
                while(left < n - 1 && nums[left] == nums[left + 1]){
                    left++;
                    count++;
                }
                left = curLeft;
                int curRight = right;
                while(right > 0 && nums[right] == nums[right - 1]){
                    right--;
                    count++;
                }
                right = curRight;
                left++;
                right--;
            }else if(nums[right] - nums[left] > k){
                right--;
            }else{
                left++;
            }
        }
        return count;
    }
}
class CountKDifferenceImpl3 implements CountKDifference{
    final static int[] TEST_01_NUMS = new int[]{1,2,2,1};
    final static int TEST_01_K = 1;

    public static void main(String[] args) {
        new CountKDifferenceImpl3().countKDifference(TEST_01_NUMS,TEST_01_K);
    }

    /**
     * o(n),o(n)
     * 哈希表，
     * @param nums
     * @param k
     * @return
     */
    @Override
    public int countKDifference(int[] nums, int k) {
        Map<Integer, Integer> freq = new HashMap<>();
        int count = 0;
        for (int i = nums.length - 1; i >= 0; i--) {
            int num = nums[i];
            /*
                处理计数
             */
            int freq1 = freq.getOrDefault(num + k, 0);
            int freq2 = freq.getOrDefault(num - k, 0);
            count = count + freq1 + freq2;

            /*
                维护map
             */
            int value = freq.getOrDefault(num, 0);
            freq.put(num, value + 1);
        }
        return count;
    }
}